package 排序算法;

import java.util.Arrays;
import java.util.Random;


//升序排序//        System.out.println(Arrays.toString(arr));
public class Test1 {
    //冒泡排序
    public int[] fun1(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {//进行多少趟数
            Boolean flag = true;
            for (int j = 1,k = 0; j < arr.length - i; j++,k++) {
                if(arr[k] > arr[j]){
                    int tep = arr[k];
                    arr[k] = arr[j];
                    arr[j] = tep;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
        return arr;
    }
    //插入排序
    public int[] fun2(int[] arr){
        for (int i = 0;i < arr.length - 1;i++){//进行插入次数
//            for(int j = i + 1,k = 0;k < j;k++){
//                //1.找到插入的位置
//                if(arr[k] > arr[j]){
//                    //2.进行插入
//                    insert(arr,k,j);
//                }
//            }
            int k = half(arr,i+1);
//            2.进行插入
            insert(arr,k,i+1);
        }
        return arr;
    }
    //插入排序（改进：在查找插入位置过程中使用二分法）
    private int half(int[] arr,int j){
        int left = 0;
        int right = j - 1;
        int k = (left + right)/2;
        while (left != right && k != 0){
            if(arr[k - 1] < arr[j] && arr[k] > arr[j]){
                break;
            }
            if(arr[j] > arr[k]){
                left = k + 1;
            }else {
                right = k;
            }
        }
        return k;
    }
    private void insert(int[] arr, int k,int j) {
        int tep = arr[j];
        while (j > k){
            arr[j] = arr[j - 1];
            j--;
        }
        arr[k] = tep;
    }
    //快速排序
    private static void swapQ(int[] arr,int x,int y){
        int tep = arr[x];
        arr[x] = arr[y];
        arr[y] = tep;
    }
    private static int mid1(int[] arr,int left,int right){
        //改进：标准位置等概率选择（两种：1.取中间数2.生成随机数）
        Random random = new Random();
        int i = left + random.nextInt( right - left);
//        int i = left + (right - left) / 2;
        int standard = arr[i];
        while (left < right) {
            while (left < right && arr[left] <= standard)left++;
            while (left < right && arr[right] >= standard)right--;
            swapQ(arr,left,right);
        }
        if(standard > arr[left])
            swapQ(arr, i, left);
        return right;
    }
    private static int[] mid(int[] arr,int left,int right){
        //改进：标准位置等概率选择（两种：1.取中间数2.生成随机数）
        Random random = new Random();
        int[] ret = new int[2];
        int i = left + random.nextInt( right - left + 1);
//        int i = left + (right - left) / 2;
        int start = left;
        int standard = arr[i];
        right++;
        left--;
        while (start < right) {
             if(arr[start] < standard) {
                int tep = arr[++left];
                arr[left] = arr[start];
                arr[start] = tep;
                start++;
            } else if(arr[start] > standard){
                int tep = arr[start];
                arr[start] = arr[--right];
                arr[right] = tep;
            }else start++;
        }
        ret[0] = left;//与目标值相等位置
        ret[1] = start;//与目标值大于位置
        return ret;
    }

    private static void sort(int[] arr,int left,int right){
        if(right <= left ){
            return;
        }
        int[] mid = mid(arr,left,right);
        sort(arr,mid[1],right);
        sort(arr,left,mid[0]);
    }

    private static void sort(int[] arr){
        sort(arr,0,arr.length - 1);
    }

    public static void main(String[] args) {//5,1,1,2,0,05,4,3,2,1,11111,1,1,1,0
        int[] arr = new int[]{5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

}





















